HackerRank The Coin Change Problem
https://www.hackerrank.com/challenges/coin-change/problem
解答
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'getWays' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
# 1. INTEGER n
# 2. LONG_INTEGER_ARRAY c
#
'''
10
2 5 3 6
0 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
dp2 += dp0
dp3 += dp1
dp4 += dp2
dp5 += dp3
dp6 += dp4
dp7 += dp5
dp8 += dp6
dp9 += dp7
dp10 += dp8
2 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
dp5 += dp0
dp6 += dp1
dp7 += dp2
dp8 += dp3
dp9 += dp4
dp10 += dp5
5 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2
dp3 += dp0
dp4 += dp1
dp5 += dp2
dp6 += dp3
dp7 += dp4
dp8 += dp5
dp9 += dp6
dp10 += dp7
3 1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4
dp6 += dp0
dp7 += dp1
dp8 += dp2
dp9 += dp3
dp10 += dp4
6 1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 5
'''
def getWays(n, c):
# dpi := Total number of ways to make an amount i
dp = 0 * (n+1)
dp0 = 1
for i in range(len(c)):
for j in range(ci, n+1):
dpj += dp[j-ci]
return dpn
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input0)
m = int(first_multiple_input1)
c = list(map(int, input().rstrip().split()))
# Print the number of ways of making change for 'n' units using coins having the values given by 'c'
ways = getWays(n, c)
fptr.write(str(ways) + '\n')
fptr.close()
テーマ
#dp
提出
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'getWays' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
# 1. INTEGER n
# 2. LONG_INTEGER_ARRAY c
#
'''
10
2 5 3 6
- sort
c = 2,3,5,6
- dpij := use c:i and use j numbers
-- dp00 = 0,
-- dp01 = 2,
-- dp02 = 4,
-- dp03 = 6,
-- dp04 = 8,
-- dp05 = 10,
-- dp10 = 0,
-- dp11 = dp10 + c1 = 3, dp00 + c1 = 3
-- dp12 = dp11 + c1 = 6, dp01 + c1 = 5
-- dp13 = dp12 + c1 = 9,8, dp02 + c1 = 7
-- dp05 = 10,
-- dp05 = 10,
'''
def getWays(n, c):
# Write your code here
c.sort()
max_use = math.ceil(n/c0) + 1
dp = [[[]] * max_use for _ in range(len(c))]
for i in range(max_use):
dp0i.append(i*c0)
for i in range(len(c)):
dpi0.append(0)
for i in range(len(c)):
for j in range(1, max_use):
for v1 in dpij-1:
dpij.append(v1+ci)
for v2 in dpi-1j-1:
dpij.append(v2+ci)
print(dp)
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input0)
m = int(first_multiple_input1)
c = list(map(int, input().rstrip().split()))
# Print the number of ways of making change for 'n' units using coins having the values given by 'c'
ways = getWays(n, c)
fptr.write(str(ways) + '\n')
fptr.close()